|
In mathematics, subshifts of finite type are used to model dynamical systems, and in particular are the objects of study in symbolic dynamics and ergodic theory. They also describe the set of all possible sequences executed by a finite state machine. The most widely studied shift spaces are the subshifts of finite type. ==Definition== Let be a finite set of symbols (alphabet). Let ''X'' denote the set ''V''Z of all bi-infinite sequences of elements of ''V'' with ''T'' the shift operator. We endow ''V'' with the discrete topology and ''X'' with the product topology. A symbolic flow or subshift is a closed ''T''-invariant subset ''Y'' of ''X'' 〔Xie (1996) p.21〕 and the associated language ''L''''Y'' is the set of finite subsequences of ''Y''.〔Xie (1996) p.22〕 Now let ''A'' be a adjacency matrix with entries in . Using these elements we construct a directed graph ''G''=(''V'',''E'') with ''V'' the set of vertices, the set of edges ''E'' defined with ''A'': so ''x''→''y'' is in ''E'' iff ''A''''x'',''y''=1. Let ''Y'' be the set of all infinite admissible sequences of edges, where by ''admissible'' it is meant that the sequence is a walk of the graph. Let ''T'' be the shift operator on such sequences; it plays the role of the time-evolution operator of the dynamical system. A subshift of finite type is then defined as a pair (''Y'', ''T'') obtained in this way. If the sequence extends to infinity in only one direction, it is called a one-sided subshift of finite type, and if it is bilateral, it is called a two-sided subshift of finite type. Formally, one may define the sequence of edges as : This is the space of all sequences of symbols such that the symbol ''p'' can be followed by the symbol ''q'' only if the (p,q)th entry of the matrix ''A'' is 1. The space of all bi-infinite sequences is defined analogously: : The shift operator ''T'' maps a sequence in the one- or two-sided shift to another by shifting all symbols to the left, i.e. : Clearly this map is only invertible in the case of the two-sided shift. A subshift of finite type is called transitive if ''G'' is strongly connected: there is a sequence of edges from any one vertex to any other vertex. It is precisely transitive subshifts of finite type which correspond to dynamical systems with orbits that are dense. An important special case is the full ''n''-shift: it has a graph with an edge that connects every vertex to every other vertex; that is, all of the entries of the adjacency matrix are 1. The full ''n''-shift corresponds to the Bernoulli scheme without the measure. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Subshift of finite type」の詳細全文を読む スポンサード リンク
|